package com.eugenes.collections;

import java.util.Comparator;
import java.util.Random;

public class MyCollections {

    private static final Random RANDOM = new Random();

    public static <T> void swap(MyList<T> list, int i, int j) {
        T element = list.get(i);
        list.set(i, list.get(j));
        list.set(j, element);
    }

    private static <T> void quicksort(MyList<T> list,
            Comparator<? super T> comparator, int begin, int end) {
        if (end - begin <= 1) {
            return;
        }

        int pivotPos = RANDOM.nextInt(end - begin);
        T pivot = list.get(begin + pivotPos);
        swap(list, begin + pivotPos, end - 1);

        int firstIndex = begin;
        for (int i = begin; i < end - 1; ++i) {
            T current = list.get(i);
            if (comparator.compare(pivot, current) > 0) {
                swap(list, i, firstIndex);
                ++firstIndex;
            }
        }
        swap(list, firstIndex, end - 1);

        quicksort(list, comparator, begin, firstIndex);
        quicksort(list, comparator, firstIndex + 1, end);
    }

    private static <T> void insertionSort(MyList<T> list,
            Comparator<? super T> comparator) {
        // array for internal use only
        @SuppressWarnings("unchecked")
        T[] data = (T[]) list.toArray();

        for (int i = 0; i < data.length; ++i) {
            boolean swapped = false;
            for (int j = 0; j < data.length - i - 1; ++j) {
                if (comparator.compare(data[j], data[j+1]) > 0) {
                    swapped = true;
                    T temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
            if (!swapped) {
                break;
            }
        }

        for (int i=0; i<list.size(); ++i) {
            list.set(i, data[i]);
        }
    }

    public static <T> void sort(MyList<T> list,
            Comparator<? super T> comparator) {

        if (list instanceof RandomAccess) {
            quicksort(list, comparator, 0, list.size());
        } else {
            insertionSort(list, comparator);
        }
    }

    public static <T extends Comparable<? super T>>
            void sort(MyList<T> list) {
        sort(list, new Comparator<T>() {
            @Override
            public int compare(T o1, T o2) {
                return o1.compareTo(o2);
            }
        });
    }

    public static <T> void copy(MyList<T> src, MyList<? super T> dest) {
        dest.addAll(src);
    }

    public static <T> void reverse(MyList<T> list) {
        for (int i = 0; i < list.size() / 2; ++i) {
            swap(list, i, list.size() - i - 1);
        }
    }

    public static <E extends Comparable<? super E>, T extends MyList<E>&RandomAccess>
            int binarySearch(T list, E obj) {
        int BAD = 0;
        int GOOD = list.size() - 1;
        while (GOOD - BAD > 1) {
            int med = BAD + ((GOOD - BAD) >> 1);
            E medElement = list.get(med);
            if (medElement.compareTo(obj) < 0) {
                BAD = med;
            } else {
                GOOD = med;
            }
        }

        if (list.get(BAD).compareTo(obj) >= 0) {
            return BAD;
        } else if (list.get(GOOD).compareTo(obj) >= 0) {
            return GOOD;
        } else {
            return GOOD + 1;
        }
    }
}
